package algo

import (
	"math"
)

// 计算最小 cost 的 位置
// 输入 m 是题目中的矩阵（二维数组），行代表降落区域，列代表无人机（下标都是从 0 算起，与题目中从 1 算起不一样）。
// 按照题目要求，一个区域只能放一架无人机，所以 行数 大于等于 列数。
// 输出的 positions 是一维数组，代表 cost 最小的情况下 每一架无人机的 停放区域（从 0 算起），所以数组长度等于 m 矩阵的 列数。
// 输出的 minCost 代表最小 cost 的取值
// 算法的思路是用递归，回溯
// 当 矩阵的 行数 等于 1 则 列数 肯定也等于 1，那么 positions 是只有 一个元素 0 的数组，minCost 则是 m[0][0].
// 当 矩阵的 行数 大于 1 的时候，不管是多少，都可以 矩阵 看成 2 列 的矩阵，即第一列是第一列，后面不管多少列都看成是一个整体(子矩阵)作为第二列。
// 递归计算 子矩阵，还是上面的逻辑。
func CalcBestPositions(m [][]float64) (positions []int, minCost float64) {
	rowCnt := len(m)
	if rowCnt == 0 {
		return
	}
	colCnt := len(m[0])
	if colCnt == 0 {
		return
	}
	if rowCnt == 1 {
		// according to the requirement, rowCnt >= colCnt, so colCnt should be 1 in this case
		return []int{0}, m[0][0]
	}

	minCost = math.MaxInt16
	positions = make([]int, colCnt)
	subM := make([][]float64, rowCnt-1) // make a sub matrix whose size is (rowCnt-1, colCnt-1)
	for r := 0; r < rowCnt; r++ {
		if m[r][0] >= minCost {
			continue
		}
		for i := 0; i < r; i++ {
			subM[i] = m[i][1:]
		}
		for i := r + 1; i < rowCnt; i++ {
			subM[i-1] = m[i][1:]
		}
		ps, cost := CalcBestPositions(subM)
		if cost < minCost {
			cost += m[r][0]
			if cost < minCost {
				minCost = cost
				positions[0] = r
				for i, p := range ps {
					if p >= r {
						p++
					}
					positions[i+1] = p
				}
			}
		}
	}
	return
}
